package club.xiaojiawei.graph;

import java.util.Arrays;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 6/24/22 12:58 AM
 * @question 685. 冗余连接 II
 * @description 在本问题中，有根树指满足以下条件的 有向 图。该树只有一个根节点，所有其他节点都是该根节点的后继。该树除了根节点之外的每一个节点都有且只有一个父节点，而根节点没有父节点。
 * 输入一个有向图，该图由一个有着 n 个节点（节点值不重复，从 1 到 n）的树及一条附加的有向边构成。附加的边包含在 1 到 n 中的两个不同顶点间，这条附加的边不属于树中已存在的边。
 * 结果图是一个以边组成的二维数组 edges 。 每个元素是一对 [ui, vi]，用以表示 有向 图中连接顶点 ui 和顶点 vi 的边，其中 ui 是 vi 的一个父节点。
 * 返回一条能删除的边，使得剩下的图是有 n 个节点的有根树。若有多个答案，返回最后出现在给定二维数组的答案。
 */
public class FindRedundantDirectedConnection685 {

    public static void main(String[] args) {
        var test = new FindRedundantDirectedConnection685();
        int[] result = test.findRedundantDirectedConnection2(new int[][]{{2,1},{3,1},{4,2},{1,4}});
        System.out.println(Arrays.toString(result));
    }

    /**
     * 官方-查并集
     * 时间复杂度：O(nlogn)
     * 空间复杂度：O(n)
     * @param edges
     * @return
     */
    public int[] findRedundantDirectedConnection(int[][] edges) {
        int n = edges.length;
        UnionFind uf = new UnionFind(n + 1);
        int[] parent = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            parent[i] = i;
        }
        int conflict = -1;
        int cycle = -1;
        for (int i = 0; i < n; ++i) {
            int[] edge = edges[i];
            int node1 = edge[0], node2 = edge[1];
            if (parent[node2] != node2) {
                conflict = i;
            } else {
                parent[node2] = node1;
                if (uf.find(node1) == uf.find(node2)) {
                    cycle = i;
                } else {
                    uf.union(node1, node2);
                }
            }
        }
        if (conflict < 0) {
            return new int[]{edges[cycle][0], edges[cycle][1]};
        } else {
            int[] conflictEdge = edges[conflict];
            int[] redundant;
            if (cycle >= 0) {
                redundant = new int[]{parent[conflictEdge[1]], conflictEdge[1]};
            } else {
                redundant = new int[]{conflictEdge[0], conflictEdge[1]};
            }
            return redundant;
        }
    }

    static class UnionFind {
        int[] ancestor;

        public UnionFind(int n) {
            ancestor = new int[n];
            for (int i = 0; i < n; ++i) {
                ancestor[i] = i;
            }
        }

        public void union(int index1, int index2) {
            ancestor[find(index1)] = find(index2);
        }

        public int find(int index) {
            if (ancestor[index] != index) {
                ancestor[index] = find(ancestor[index]);
            }
            return ancestor[index];
        }
    }

    /**
     * 民间-查并集（nb）
     * @param edges
     * @return
     */
    public int[] findRedundantDirectedConnection2(int[][] edges) {
//        path[i] = n 表示i节点的第一个入度在edges里的下标
        int[] path = new int[edges.length + 1];
        Arrays.fill(path,  -1);
        int path2 = -1;
        for(int i = 0; i < edges.length; i++) {
//            不等于-1表示已经存储入度下标了，即现在有两个入度了。
            if (path[edges[i][1]] != -1) {
//                存储第二个入度的下标
                path2 = i;
            } else {
                path[edges[i][1]] = i;
            }
        }
//        两种情况：
        //情况一：边中出现了入度为2的点
        if (path2 != -1) {
            int node = edges[path2][1];
            int firstEdge = path[node];
            int temp = firstEdge;
            while (temp != -1) {
                int index = edges[temp][0];
                temp = path[index];
                if (index == node) {
                    //找到第一条边引发的环，案例：{2,1},{3,1},{4,2},{1,4}
                    return edges[firstEdge];
                }
            }
//            案例：[1,2],[1,3],[2,3]
            return edges[path2];//前一条边无环则直接删除后一条边
        }
        //情况二：所有点的入度都为1，必有环，要删除环中最后输入的边，案例：[1,2],[2,3],[3,4],[4,1],[1,5]
        boolean[] visited = new boolean[edges.length + 1];
        int index = 1;
//        进入环内，找到环内的点，找到环内的点才能循环找到最后面的边，然后删除
        while (!visited[index]) {
            visited[index] = true;
            int firstEdge = path[index];
            index = edges[firstEdge][0];
        }
        int result = path[index];
        int temp = edges[result][0];
        int edgeNum;
//  循环一圈找到最后面的边
        while (temp != index) {
            edgeNum = path[temp];
//            记录下标最大，即最后面的边
            result = Math.max(result, edgeNum);
            temp = edges[edgeNum][0];
        }
        return edges[result];
    }
}